package goleetcode

type LFUCache struct {
	minfreq  int
	capacity int
	keyMap   map[int]*LfuNode
	freqMap  map[int]*DoubleLinkedList
}

type LfuNode struct {
	key  int
	val  int
	freq int
	prev *LfuNode
	next *LfuNode
}

type DoubleLinkedList struct {
	dummyHead, dummyTail *LfuNode
	size                 int
}

func Constructor(capacity int) LFUCache {
	lfu := &LFUCache{
		minfreq:  0,
		capacity: capacity,
		keyMap:   map[int]*LfuNode{},
		freqMap:  map[int]*DoubleLinkedList{},
	}
	return *lfu
}

func (this *LFUCache) Get(key int) int {
	if this.capacity == 0 {
		return -1
	}
	if this.keyMap[key] == nil {
		return -1
	}
	node := this.keyMap[key]
	val := node.val
	freq := node.freq
	this.freqMap[freq].remove(node)
	// 如果链表为空，需要在哈希表中删除
	if this.freqMap[freq].size == 0 {
		delete(this.freqMap, freq)
		if this.minfreq == freq {
			this.minfreq++
		}
	}
	list := &DoubleLinkedList{}

	if this.freqMap[freq+1] != nil {
		list = this.freqMap[freq+1]
	}

	list.addFirst(&LfuNode{
		key:  key,
		val:  val,
		freq: freq + 1,
	})

	this.freqMap[freq+1] = list
	this.keyMap[key] = this.freqMap[freq+1].getHead()
	return val
}

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return;
	}
	if this.keyMap[key] == nil {
		if len(this.keyMap) == this.capacity {
			node := this.freqMap[this.minfreq].getTail()
			delete(this.keyMap, node.key)
			this.freqMap[this.minfreq].remove(node)
			if this.freqMap[this.minfreq].size == 0 {
				delete(this.freqMap, this.minfreq)
			}
		}
		list := &DoubleLinkedList{}

		if this.freqMap[1] != nil {
			list = this.freqMap[1]
		}

		list.addFirst(&LfuNode{
			key: key,
			val: value,
			freq: 1,
		})

		this.freqMap[1] = list
		this.keyMap[key] = this.freqMap[1].getHead()
	} else {
		node := this.keyMap[key]
		freq := node.freq
		this.freqMap[freq].remove(node)
		if this.freqMap[freq].size == 0 {
			delete(this.freqMap, freq)
			if this.minfreq == freq {
				this.minfreq++
			}
		}
		list := &DoubleLinkedList{}

		if this.freqMap[freq+1] != nil {
			list = this.freqMap[freq+1]
		}
		
		list.addFirst(&LfuNode{
			key: key,
			val: value,
			freq: freq + 1,
		})
		this.freqMap[freq + 1] = list
		this.keyMap[key] = this.freqMap[freq + 1].getHead()
	}
}

func (this *DoubleLinkedList) addFirst(node *LfuNode) {
	preHead := this.dummyHead.next
	node.prev = this.dummyHead
	this.dummyHead.next = node
	node.next = preHead
	preHead.prev = node
	this.size++
}

func (this *DoubleLinkedList) remove(node *LfuNode) {
	prev := node.prev
	next := node.next
	prev.next = next
	next.prev = prev
	this.size--
}

func (this *DoubleLinkedList) getHead() *LfuNode {
	return this.dummyHead.next
}

func (this *DoubleLinkedList) getTail() *LfuNode {
	return this.dummyTail.prev
}
